package Algorithm.backTracking;

import java.util.*;

/**
 * 90. 子集 II https://leetcode.cn/problems/subsets-ii
 * 题目简述：给你一个整数数组nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集，包括空集）。
 * todo 划分子集问题 https://leetcode.cn/problems/partition-to-k-equal-sum-subsets
 *  https://leetcode.cn/problems/fair-distribution-of-cookies/
 */
public class SubsetsWithDup {

    /**
     * 这题与77.子集的不同之处在于，如果按照一般的回溯遍历过程，可能会出现[1,2,3] [1,3,2]这样的重复子集，或者一次路径选择列表中有多个相同元素
     * 故需先对数组进行排序，并且在路径选择列表中进行去重，使得路径都是升序排列且不会重复选择相同路径，这样就避免了重复序列
     *
     * 思路：回溯算法。关键点在于要先对数组排序（避免出现[1,2,3] [1,3,2]这样的重复子集），然后对同层选择列表去重
     * 回溯递归函数参数：（结果集，已选择路径，下一步路径选择列表：数组nums中下标begin开头的子数组）
     * 回溯递归函数体：1.若begin==length，则数组已遍历完 直接return
     *              2.遍历当前选择列表[begin,length-1]：同层去重，若与同层前一个元素相同则略过。否则将选择加入路径，将path加入结果集，
     *               然后递归下一步选择列表，完毕后撤销上一步选择，继续遍历同层其他选择
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        //先排序
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        Deque<Integer> path = new ArrayDeque<>();
        backTracking(result, path, nums, 0);
        return result;
    }

    public void backTracking(List<List<Integer>> result, Deque<Integer> path, int[] nums, int begin) {
        if(begin == nums.length) return;
        for(int i = begin;i < nums.length;i++) {
            //每一步的路径选择列表去重，注意路径列表是从begin开始
            //因为已经排序过了，故只需要看这个路径元素与前一个元素是否相同，若相同则略过
            if(i > begin && nums[i] == nums[i-1]) continue;
            path.add(nums[i]);
            result.add(new ArrayList<>(path));
            backTracking(result, path, nums, i+1);
            path.removeLast();
        }
    }
}
